The present invention refers to a method and an apparatus for switching data between a set of input bitstreams and a set of output bitstreams in a circuit switched time division multiplexed network, each of said bitstreams being divided into recurring frames and each of said frames being divided into time slots.
Today, new types of circuit switched communication networks are being developed for the transfer of information using time division multiplexed bitstreams, wherein the bitstreams of the network are divided into recurrent, typically fixed size frames, each frame in turn being divided into time slots.
An example of such a network, referred to as a DTH (Dynamic synchronous Transfer Mode) network, is described in xe2x80x9cThe DTM Gigabit Networkxe2x80x9d, Christer Bohm, Per Lindgren, Lars Ramfelt, and Peter Sjxc3x6din, Journal of High Speed Networks, 3(2):109-126, 1994, and in xe2x80x9cMulti-gigabit networking based on DTMxe2x80x9d, Lars Gauffin, Lars Hxc3xa5kansson, and Bjxc3x6rn Pehrson, Computer networks and ISDN Systems, 24(2):119-139, April 1992.
In such a network, so called switch nodes, each connected to at least two bitstreams, are used to switch time slot data between different bitstreams, more specifically between time slot positions on different bitstreams. If, for example, a circuit (or xe2x80x9cchannelxe2x80x9d) is defined by a first set of time slot positions on a first bitstream and a second set of time slot positions on a second bitstream, a switch node is typically used to transfer or copy time slot data from the first set of time slot positions to the second set of time slot positions.
According to prior art, switches in circuit switched time division multiplexed networks use control memories that map incoming slot positions to outgoing slot positions. Such mapping may involve both a mapping in the time domain, i.e. control of the order in which time slot data are written into each bitstream, and a mapping in the space domain, i.e. controlling which time slot data goes to which bitstream. For general background, so-called time-space-time (TST) switches are described in xe2x80x9cData and Computer Communicationsxe2x80x9d, 4th ed., by Williams Stallings, Macmillan Publishing Company.
As an example of prior art switches, U.S. Pat. No. 4,005,272 (Collins et al.), describes a switch apparatus wherein incoming bitstream frames are stored in respective inlet memories and wherein outgoing bitstream frames are stored in respective outlet memories. Based upon information provided in a plurality of control memories, time slot data stored in said inlet memories are transferred to said outlet memories via a space switch. A first control memory is used to designate the inlet memory entry that is currently connected to the space switch, thereby providing a time switching function at the inlet port. Another control memory is used to designate the outlet memory entry that is currently connected to the space switch, thereby correspondingly providing a time switching function at the outlet port. Also, further control memories are provided to control which cross-connections that are to be made over within the space switch.
A disadvantage of switch nodes of the above mentioned kinds is that they do not allow arbitrary communication between input and output ports, i.e. they show limitation as to the possibilities of arbitrary switching time slots in space and time, which consequently also limits switching speed and capacity. Because of the operation features of a space switch of the kind used in, e.g., U.S. Pat. No. 4,005,272, any-to-any switching is typically rendered impossible. In most cases, a first selection of mapping of a specific input time slot position to a specific output time slot position will directly imply restrictions as to a second selection of further mapping. This of course also limits the possibilities of providing space and time multicasting and/or broadcasting.
Furthermore, in prior art, input and output ports are connected together using a shared medium that handles the aggregated switching capacity of the input ports to not provide blocking. This typically requires switch internal processing at a bit rate of several times the bit rate of the network bitstreams, which of course limits the scalability of such a design.
An object of the invention is to provide a switching apparatus and method that provides greater freedom as to the possibilities of arbitrarily switching time slots in space and time.
Another object of the invention is to provide a solution that efficiently handles time and space multicasting and broadcasting channels.
Another object of the invention is to provide a simple and fast mechanism for switching between multiple incoming and outgoing bitstreams which are arbitrarily phase shifted.
Another object of the invention is to increase the general switching speed and capacity.
Yet another object of the invention is to provide a scaleable switching system, wherein smaller switches may easily be integrated into forming larger switches.
The above mentioned and other objects are achieved by the invention as defined in the accompanying claims.
According to the invention, there is provided a method and an apparatus for switching data between a set of input bitstreams and a set of output bitstreams in a circuit switched time division multiplexed network, each of said bitstreams being divided into recurring frames and each of said frames being divided into time slots. The input bitstreams are received and the frames thereof are temporarily stored in a set of memory means (for simplicity referred to below as a set of frame buffers). Each frame buffer is used for temporarily storing frames of a respective bitstream of said input bitstreams. For each frame of each one of said output bitstreams and in sequence accordance with the order that said time slot data is to be transmitted therein, time slot data is selectively read from frames temporarily stored in said set of frame buffers. Said time slot data, as selectively read from said frame buffers, are then transmitted into allocated time slots of said output bitstreams.
Consequently, in a switch embodying the invention, each input port is associated with a respective frame buffer for temporary storing of frames that are received at said input port. All output ports can, independently of one another, read data from any one or more of said frame buffers in a non-blocking manner. A full switch thus comprises a set of frame buffers, each being arranged in a 1-to-many (one input to many outputs) fashion.
According to the invention, time and space switching is advantageously accomplished in one single integrated step by the selective reading of data from the frames that are stored in said set of frame buffers, only requiring one single read control function (for example implemented using a so called slot mapping table) for controlling said selective reading for each output bitstream.
Furthermore, as each input bitstream is written into a respective frame buffer, and time slot data for the output bitstreams are read out from said frame buffers as requested for output, a switch according to the invention will only have to be able to operate at a rate essentially corresponding to the bitstream bit-rate. However, this does not prevent the invention from being used in relation to memory means operating at a bit-rate exceeding wire speed.
Also, using the invention, no multiplexing of time slots from different bitstreams is needed at the input side (or corresponding demultiplexing at the output side) of the memory means, in contrast to what is often encountered in prior art.
According to a preferred embodiment of the invention, said frame buffers are realized by means of multiported random access memories (RAM), which allows insertion and retrieval to be performed independently and without phase synchronization.
By using RAMs with multiple read ports, each output bitstream will, independently of others, retrieve its own time slot data and preferably collect it using lines private to said output bitstream, thus providing a non-blocking operation. Therefore, there is no need for mutual exclusion or complicated reservation schemes on a shared resource. It also follows that the concept does not require a higher communication Speed in any part of the design compared to the speed at which each line receives input or transmits output. Consequently, a switch embodying the invention will show a significant freedom of operation with respect to the possibilities of arbitrary switching of time slots in time and space as compared to prior art switches.
As is understood, a multi-ported random access memory as suggested above may provide a plurality of actual physical read ports or, for example, one single physical port that in turn provides a plurality of virtual read ports (one private to each output port), as long as the memory means provides support for a selective read access (in the time slot sequential order of the respective output frame) to the output ports as suggested according to the invention. Consequently, as mentioned above, operation within the memory means as such may still, if so desired or required, use a bit rate that exceeds the bitstream bit-rate.
As the frame buffers are repeatedly updated at a high rate, an implementation based on dynamic RAM (DRAM) can be envisaged without a need for memory refresh.
As mentioned, according to a preferred embodiment of the invention, all output ports read data from said set of frame buffers independently of one another, and the time slot data is preferably transferred from said frame buffers to the output ports on lines private to each output port.
Typically, each one of said frame buffers will comprise a plurality of time slot data entries, wherein each time slot data entry of a frame buffer is arranged to store time slot data from a respective recurring time slot position in the sequence of time slots of the input bitstream that is associated with said frame buffer.
Since time slot data may be read from any time slot entry of said frame buffers to different output ports, the mechanism for broadcasting and multicasting (i.e. sending data from one input port to several output ports) is implicitly provided.
Preferable, a switch apparatus according to the invention comprises means, for example in the form of a control memory (xe2x80x9cslot mapping tablexe2x80x9d), for providing, for those time slots of a frame of each output bitstream that are allocated to receive time slot data from the input bitstreams, each one thereof with a respective identification of an associated time slot data entry of said frame buffers, said time slot data entry providing the time slat data for the respective allocated time slot.
Such an identification may for example be an identification uniquely identifying a frame buffer and an entry thereof providing the time slot data to be transmitted into the output time slot associated with said identification, an identification stating that write access to the corresponding output time slot does not belong to the switch and that the output time slot shall not be provided with time slot data from said input bitstream, an identification that an idle pattern shall be generated by the switch and transmitted into the corresponding output time slot, or an identification that time slot data received from another switch shall be transmitted into said corresponding time slot. Thus the designation of where from to collect data for each output time slot provides several new possibilities for switching data. For example, the latter of the four exemplified types of identifications above makes it possible to connect several switches in a simple manner into forming a larger switch, thereby increasing the switching possibilities without essentially complicating implementation.
Preferably, each input frame buffer has capacity to hold three sequential frames of the input bitstream in respective frame storage areas, also referred to as frame pages or columns, of said frame buffer. The use of three frame pages per input bitstream is meant to ensure switching consistency, i.e. making sure that the selective reading from a frame or page does not take place before the input writing of that specific frame or page is completed. According to the preferred embodiment, one page is needed to enable re-mapping of time slot in the time domain, another one is needed for parallel storage in a double buffering fashion, and the third page is needed to handle any frame phase difference between the input port writing into said frame buffer and the output ports reading from said frame buffer, a difference which is constrained to one page as a result of the general synchronization of, for example, a DTM network.
Each one of the input and output ports is typically controlled by a respective frame synchronization signal, which in turn advances internal pointers to identify the frame page currently used for writing (at an input port) or the frame pages that are currently used for reading (at an output port). The time slots of an input bitstream are written into storage in sequential order, while the outputs are read from said frame buffers using random access among the entries of the pages currently selected for selective reading.
Time slots and frames are hence clocked using clock and frame synchronization signals local to each port, and the frame buffers are accessed by the ports according to the respective local frame synchronization. An underlying assumption is that the frame synchronization signals never have a skew, i.e. a phase difference between an input bitstream and an output bitstream, of more than one frame, i.e. there is no accumulated frame difference (drift), which is a criteria that is accomodated in, for example, a DTM network, the invention therefore being of special intererst in such a network.
The frame synchronization of an input bitstream preferably controls a write slot counter, which advances a write pointer designating a time slot entry of the respective frame buffer to the next time slot entry upon each received time slot (Upon frame synch, the write slot counter is preferably reset to start at the lowest slot in the next frame). The frame synchronization of the input bitstream preferably also controls a write page select block, one designating a page of the respective frame buffer, which enables one of the three frame pages of the buffer for write access. (Upon frame synch, the next frame page is selected in a circular fashion.)
The frame synchronization of an output bitstream preferably controls an output slot counter, which at each output time slot advances a pointer in said time slot table for deriving information as to where time slot data for the subject output time slot is to be collected. (Upon frame synch, the output slot counter is preferably reset to start at the lowest slot in the next output frame). The frame synchronization of the output bitstream preferably also controls a read page select block, which selects which frame pages, of respective frame buffers, that may currently be used for selective read access. Upon frame synch, the next page is selected in a circular fashion.
Accordingly, one advantage of the invention is that control of the operation at each port of the switch is provided by a frame synchronization local to each respective port, thus eliminating the need for providing complicated cross-related synchronization mechanism between the different input and output ports.
According to a further developed embodiment of the invention, said read page selection is also controlled by a so called page offset and bypass feature, as activated on a slot per slot basis by the slot mapping table. The bypass mode provides the option to gain read access one frame ahead of the actual read access pointer, which reduces the latency through the switch but puts constraints on the slot allocation in order to ensure that no access conflict or inconsistency occurs during time domain re-mapping.
According to yet another embodiment of the invention, a mechanism for performing automatic updates of the slot mapping tables is provided, i.e. to simultaneously update more than one time slot table and more than one time slot entry thereof in a fashion which preserves consistency.
A preferable implementation of switching according to the invention is in a DTM network. The basic topology of a DTM network is preferably a bus with two unidirectional, multi-access optical fibers connecting a number of nodes. Note, however, that the topology may just as well be realized by any other kind of structure, e.g. a ring structure or a hub structure.
The bandwidth of each wavelength on the bus, i.e. each bitstream on each fiber, is divided into fixed length, typically 125 xcexcs, frames which in turn are divided into fixed size, typically 64 bit, time slots. The number of slots in a cycle thus depends on the network""s bit-rate. The time slots are divided into two groups, control slots and data slots. Control slots are used for transferring of signaling messages between said nodes for the network""s internal operation. The data slots are used for the transfer of data between end users or applications using said nodes for access to the DTM network.
The nodes of the DTM network are typically arranged to dynamically establish, modify, and terminate channels on said bitstreams by dynamically allocating selected time slots to the respective channel. Hence, the allocation of both time slots and data slots to different nodes or end users may be dynamically adjusted as network load changes. As is understood, there is essentially no header or address information embedded in the data slots in this kind of circuit switching.
For a more detailed description of the DTM technology, reference is made to the above mentioned references xe2x80x9cThe DTM Gigabit Networkxe2x80x9d and xe2x80x9cMulti-gigabit networking based on DTMxe2x80x9d.
The above mentioned and other aspects and features of the invention will be more fully understood from the following description, with reference to the accompanying drawings, of exemplifying embodiments thereof.